package NewCoder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class BM58 {
    ArrayList<String> list=new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        int n=str.length();
        char[] s=str.toCharArray();
        Arrays.sort(s);
        HashMap<Integer,Character> map=new HashMap<>();
        dfs(s,n,list,new StringBuilder(),map);
        return list;
    }
    private void dfs(char[] s,int len,ArrayList<String> list,StringBuilder sb,
                     HashMap<Integer,Character> map  ){
        if(sb.length()==len){
            if(!list.contains(sb.toString())){
                list.add(sb.toString());
            }
            return;
        }
        for(int k=0;k<len;k++){
            if(map.containsKey(k)){
                continue;
            }
            sb.append(s[k]);
            map.put(k,s[k]);
            dfs(s,len,list,sb,map);
            sb.deleteCharAt(sb.length()-1);
            map.remove(Integer.valueOf(k));
        }
    }
}
